翻訳と辞書
Words near each other
・ Unionville, Ontario
・ Unionville, Orange County, New York
・ Unionville, Pennsylvania
・ Unionville, Talbot County, Maryland
・ Union, Rock County, Wisconsin
・ Union, South Carolina
・ Union, Surigao del Norte
・ Union, University & Schools Club
・ Union, Vernon County, Wisconsin
・ Union, Virginia
・ Union, Washington
・ Union, Waupaca County, Wisconsin
・ Union, West Virginia
・ Union, Wisconsin
・ Union-Castle Line
Union-closed sets conjecture
・ Union-Endicott High School
・ Union-North United Schools
・ Union-Philanthropic Society
・ Union-Rennen
・ UnionBanCal Corporation
・ Unionbank
・ UnionBank Plaza
・ Uniondale
・ Uniondale High School
・ Uniondale, Indiana
・ Uniondale, New York
・ Uniondale, Western Cape
・ Unione
・ Unione Astrofili Italiani


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Union-closed sets conjecture : ウィキペディア英語版
Union-closed sets conjecture

In combinatorial mathematics, the union-closed sets conjecture is an elementary problem, posed by Péter Frankl in 1979 and still open. A family of sets is said to be ''union-closed'' if the union of any two sets from the family remains in the family. The conjecture states that for any finite union-closed family of finite sets, other than the family consisting only of the empty set, there exists an element that belongs to at least half of the sets in the family.
==Equivalent forms==
If ''F'' is a union-closed family of sets, the family of complement sets to sets in ''F'' is closed under intersection, and an element that belongs to at least half of the sets of ''F'' belongs to at most half of the complement sets. Thus, an equivalent form of the conjecture (the form in which it was originally stated) is that, for any intersection-closed family of sets that contains more than one set, there exists an element that belongs to at most half of the sets in the family.
Although stated above in terms of families of sets, Frankl's conjecture has also been formulated and studied as a question in lattice theory. A lattice is a partially ordered set in which for two elements ''x'' and ''y'' there is a unique greatest element less than or equal to both of them (the ''meet'' of ''x'' and ''y'') and a unique least element greater than or equal to both of them (the ''join'' of ''x'' and ''y''). The family of all subsets of a set ''S'', ordered by set inclusion, forms a lattice in which the meet is represented by the set-theoretic intersection and the join is represented by the set-theoretic union; a lattice formed in this way is called a Boolean lattice.
The lattice-theoretic version of Frankl's conjecture is that in any finite lattice there exists an element ''x'' that is not the join of any two smaller elements, and such that the number of elements greater than or equal to ''x'' totals at most half the lattice, with equality only if the lattice is a Boolean lattice. As Abe (2000) shows, this statement about lattices is equivalent to the Frankl conjecture for union-closed sets: each lattice can be translated into a union-closed set family, and each union-closed set family can be translated into a lattice, such that the truth of the Frankl conjecture for the translated object implies the truth of the conjecture for the original object. This lattice-theoretic version of the conjecture is known to be true for several natural subclasses of lattices (Abe 2000; Poonen 1992; Reinhold 2000) but remains open in the general case.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Union-closed sets conjecture」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.